package com.markus.code.二叉树.leetcode;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/10 23:19
 * todo: 二叉树的最近公共祖先 ~~ 看答案做出的
 */
public class LeetCode_236 {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val = val;
        }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //在递归中一旦发现出现了p或者q就返回，或者遍历到空的节点时还有没有找到就返回为空
        if(root == null || root == p || root == q){
            return root;
        }
        //递归遍历自己的左子树，找到第一个出现pq某一节点时返回，或者遍历到尾还没找到，则返回为空
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        //遍历自己的右子树，一样的道理
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        //这步比较重要，如果这两个子树都不为空，说明这两个节点分布在以这个节点开始分叉的左右两颗子树上
        if(left != null && right != null){
            return root;
        }
        //加入pq出现在了某一颗子树上，那就返回某课子树上返回的值。
        return left != null ? left : right;
    }
}
